package offer.offer03;

import java.util.ArrayList;
import java.util.List;

/**
 * 如果是让我写二分排序的话, 我会在一个等长的新的Array中, 比当前值大的从前面写入, 比当前值小的从最后写入。
 */
public class S51数组中的逆序对 {

    public static void main(String[] args) {
        int[] nums = new int[]{1, 1, 1, 1, 1, 1};
        System.out.println(reversePairs(nums));
    }

    /**
     * 5, 二分法查找, 需要方法binarySearch的使用
     * 自己手工实现了一下binarySearch, 麻烦。
     */
    public static int reversePairs(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        List<Integer> inputList = new ArrayList<>();
        inputList.add(nums[0]);
        int reverseCount = 0;
        for(int i = 1; i < nums.length; i ++){
            int curNum = nums[i];
            int insertLoc = binarySearch(inputList, curNum, 0, inputList.size() - 1);
            reverseCount += insertLoc;
            if(insertLoc == inputList.size()){
                inputList.add(curNum);
            }else{
                inputList.add(insertLoc, curNum);
            }
        }
        return reverseCount;
    }
    /**
     * 手动做一个二分法查找, 默认list是递减的
     * 二分查找返回的是他能插入的位置, 如果是负的表示不在里面。
     */
    public static int binarySearch(List<Integer> inputList, int aimNum, int start, int end){
        int middle = (start + end) / 2;
        int middleNum = inputList.get(middle);
        int startNum = inputList.get(start);
        int endNum = inputList.get(end);
        if(middle == start){
            // start == end 或者 start == end - 1
            if(aimNum > startNum){
                return start;
            }else if(aimNum < endNum){
                return end + 1;
            }else if(aimNum == startNum){
                return start;
            }else if(aimNum == endNum){
                return end;
            }else{
                return middle + 1;
            }
        }
        if(middleNum > aimNum){
            return binarySearch(inputList, aimNum, middle + 1, end);
        }else if(middleNum < aimNum){
            return binarySearch(inputList, aimNum, start, middle - 1);
        }else{
            // 处理一下重复的部分
            while(middle >= 0 && inputList.get(middle) == aimNum){
                middle --;
            }
            return middle + 1;
        }
    }
    public static int binarySearch2(List<Integer> inputList, int aimNum, int start, int end){
        while(start < end){
            int middle = (start + end) / 2;
            int middleNum = inputList.get(middle);
            if(middleNum < aimNum){
                end = middle - 1;
            }else if(middleNum > aimNum){
                start = middle + 1;
            }else {
                return middle;
            }
        }

        return -1;
    }

}
